package com.liunian.algorithmstudy.tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class PreorderTraversal144 extends TreeNode {

    // 前序迭代
    public List<Integer> preorderTraversal(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode treeNode = deque.pollFirst();
            if (treeNode == null) {
                continue;
            }
            res.add(treeNode.val);
            if (treeNode.right != null) {
                deque.push(treeNode.right);
            }
            if (treeNode.left != null) {
                deque.push(treeNode.left);
            }
        }
        return res;
    }

    // 后序迭代
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode treeNode = deque.pollFirst();
            if (treeNode == null) {
                continue;
            }
            res.add(treeNode.val);
            if (treeNode.left != null) {
                deque.push(treeNode.left);
            }
            if (treeNode.right != null) {
                deque.push(treeNode.right);
            }
        }
        for (int i = 0; i < res.size() / 2; i++) {
            int temp = res.get(i);
            res.set(i, res.get(res.size() - 1 - i));
            res.set(res.size() - 1 - i, temp);
        }
        return res;
    }

    // 中序迭代
    public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        List<Integer> res = new LinkedList<>();
        deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode treeNode = deque.pollFirst();
            if (treeNode == null) {
                continue;
            }
            if (treeNode.right != null) {
                deque.addFirst(treeNode.right);
            }
            if (treeNode.left != null) {
                TreeNode left = treeNode.left;
                treeNode.left = null;
                treeNode.right = null;
                deque.addFirst(treeNode);
                deque.addFirst(left);
            } else {
                res.add(treeNode.val);
            }
        }
        return res;
    }

}
